package search.binarysearch;

/**
 * https://leetcode-cn.com/problems/search-in-rotated-sorted-array/
 * 旋转有序集合中查询指定值位置
 */
public class BinaryTest {

    /**
     * 旋转有序集合中查询指定值位置
     *
     * @param array 集合
     * @param value 指定值
     * @return 位置
     */
    public static int binary(int[] array, int value) {

        if (array == null || array.length == 0) {
            return -1;
        }

        int start = 0;
        int end = array.length - 1;
        int middle;
        while (start + 1 < end) {

            //middle 随着start、end 变化而变化
            middle = start + (end - start) / 2;
            if (value == array[middle]) {
                return middle;
            }

            //确定升序，还是降序
            if (array[middle] > array[start])//升序
            {
                //在start 和 middle
                if (value <= array[middle] && value >= array[start]) {
                    end = middle;
                } else {
                    start = middle;
                }
            } else {
                //降序
                if (value >= array[middle] && value <= array[end]) {
                    start = middle;
                } else {
                    end = middle;
                }

            }

        }
        if (value == array[start]) {
            return start;
        }
        if (value == array[end]) {
            return end;
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] a = {7, 8, 9, 1, 2, 3, 4, 5, 6};
        // int[] a = {6, 5, 4, 3, 2, 1, 9, 8, 7}; ??
        //int[] a = {9, 8, 7, 6, 5, 4, 3, 2, 1};
        int value = binary(a, 7);
        System.out.println(value);
    }
}
